use serde::de::{MapAccess, Visitor};
use serde::{Deserialize, Deserializer};
use std::collections::HashMap;
use std::env;
use std::fs::File;
use std::io::Read;
use std::path::PathBuf;
use std::str::FromStr;

pub fn count_provinces() -> String {
    // 使用并查集
    let data = read_json();
    let mut res = vec![-1i64; 100000];
    for (k, v) in data {
        let mut team: HashMap<String, String> = HashMap::new();
        let mut strings = Vec::new();
        for (k, v) in v.0 {
            if !team.contains_key(&k) {
                team.insert(k.clone(), k.clone());
                strings.push(k.clone());
            }
            for s in v {
                if !team.contains_key(&s) {
                    team.insert(s.clone(), s.clone());
                    strings.push(s.clone());
                }
                let fk = find(&k, &mut team);
                let fs = find(&s, &mut team);
                if fk != fs {
                    team.insert(fs.clone(), fk);
                }
            }
        }
        let mut rem: HashMap<String, bool> = HashMap::new();
        let mut cnt = 0;
        for s in strings {
            let fs = find(&s, &mut team);
            // println!("{}, {}", s.clone(), fs.clone());
            rem.entry(fs).or_insert_with(|| {
                cnt += 1;
                true
            });
        }
        let k = usize::from_str(&k).unwrap();
        res[k] = cnt;
    }
    let mut s = String::new();
    for cnt in res {
        if cnt < 0 {
            continue;
        }
        if s.is_empty() {
            s += &cnt.to_string();
            continue;
        }
        s += &format!(",{}", cnt);
    }
    s
}

fn find(s: &String, map: &mut HashMap<String, String>) -> String {
    let k = map.get(s).unwrap();
    if k != s {
        let t = find(&k.clone(), map);
        map.insert(s.clone(), t);
    }
    map[s].clone()
}

fn read_json() -> HashMap<String, Province> {
    let workspace = PathBuf::from(find_workspace_root().unwrap());
    let file_path = "topic1/solutiont2/district.json";
    let path = workspace.join(file_path);
    let mut file = File::open(path).unwrap();
    let mut json = String::new();
    file.read_to_string(&mut json).unwrap();
    let data: HashMap<String, Province> = serde_json::from_str(&json).unwrap();
    data
}

impl<'de> Deserialize<'de> for Province {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: Deserializer<'de>,
    {
        struct MyVisitor;

        impl<'d> Visitor<'d> for MyVisitor {
            type Value = Vec<(String, Vec<String>)>;

            fn expecting(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
                f.write_str("a map of abilities")
            }

            fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
            where
                M: MapAccess<'d>,
            {
                let mut res = Vec::new();
                while let Some((key, mut value)) = access.next_entry()? {
                    res.push((key, value));
                }
                Ok(res)
            }
        }
        Ok(Province(deserializer.deserialize_map(MyVisitor)?))
    }
}

#[derive(Debug, Eq, Hash, PartialEq)]
struct Province(Vec<(String, Vec<String>)>);

fn find_workspace_root() -> Option<String> {
    let mut current_dir = env::current_dir().ok()?;
    let cargo_toml_path = current_dir.join("Cargo.toml");
    if cargo_toml_path.is_file() {
        let mut file = File::open(cargo_toml_path).unwrap();
        let mut json = String::new();
        file.read_to_string(&mut json).unwrap();
        if json.contains("[workspace]") {
            return Some(current_dir.to_str().unwrap().to_string());
        }
    }

    while current_dir.parent().is_some() {
        current_dir = current_dir.parent()?.to_path_buf();
        let cargo_toml_path = current_dir.join("Cargo.toml");
        if cargo_toml_path.is_file() {
            let mut file = File::open(cargo_toml_path).unwrap();
            let mut json = String::new();
            file.read_to_string(&mut json).unwrap();
            if json.contains("[workspace]") {
                return Some(current_dir.to_str().unwrap().to_string());
            }
        }
    }

    None
}